import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-04-11
 * Time: 21:18
 */

//139.单词拆分
class Solution7 {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        //优化1：c创建HashMap
        Set<String> hash = new HashSet(wordDict);
        //1.创建dp表
        boolean[] dp = new boolean[n+1];
        //2.初始化
        dp[0] = true; //如果是false后面都不需判断就是false了
        s = " "+s; //处理下标的映射关系
        //3.状态转移
        for(int i = 1; i <= n; i++) {
            for(int j = i; j >= 1; j--) {
                if(dp[j-1] && hash.contains(s.substring(j,i+1))) {
                    dp[i] = true;
                    break; //优化2
                }
            }
        }
        //4.填表顺序
        //5.返回值
        return dp[n];
    }
}
